//class Solution {
//public:
//	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
//		vector<TreeNode*> result;
//		unordered_map<string, int> mp;
//		helper(root, result, mp);
//		return result;
//	}
//	string helper(TreeNode*root, vector<TreeNode*>&result,
//		unordered_map<string, int>&mp)
//	{
//		string str;
//		if (!root) return "#";
//		str = to_string(root->val) + ' ' + helper(root->left, result, mp) + ' ' + helper(root->right, result, mp);
//		if (mp[str] == 1) result.push_back(root);
//		mp[str]++;
//		return str;
//	}
//};

//class Solution {
//public:
//	int numSpecial(vector<vector<int>>& mat) {
//		int n = mat.size();
//		if (n == 0) return 0;
//		int m = mat[0].size();
//		vector<int> row(n);
//		vector<int> col(m);
//		for (int i = 0; i<n; i++) {
//			for (int j = 0; j<m; j++) {
//				if (mat[i][j] == 1) {
//					row[i] ++;
//					col[j] ++;
//				}
//			}
//		}
//		int ans = 0;
//		for (int i = 0; i<n; i++) {
//			for (int j = 0; j<m; j++)
//			{
//				if (row[i] == 1 && col[j] == 1 && mat[i][j] == 1) {
//					ans++;
//				}
//			}
//		}
//		return ans;
//	}
//};

//class Solution {
//public:
//	class Greater
//	{
//	public:
//		bool operator()(vector<int>& x1, vector<int>& x2)
//		{
//			return x1[1]<x2[1];
//		}
//	};
//	int findLongestChain(vector<vector<int>>& pairs) {
//		sort(pairs.begin(), pairs.end(), Greater());
//		int res = 1;
//		int j = 0;
//		for (int i = 1; i<pairs.size(); i++)
//		{
//			if (pairs[i][0]>pairs[j][1])
//			{
//				j = i;
//				res++;
//			}
//		}
//
//
//		return res;
//	}
//};

//class Solution {
//public:
//	int func(TreeNode* root, int _val)
//	{
//		if (root == nullptr || root->val != _val)
//			return 0;
//
//		int left = 1 + func(root->left, _val);
//		int right = 1 + func(root->right, _val);
//		return left>right ? left : right;
//	}
//
//	void func1(TreeNode* root, int & res)
//	{
//		if (root == nullptr)
//			return;
//
//		int left = func(root->left, root->val);
//		int right = func(root->right, root->val);
//		if (left + right>res)
//			res = left + right;
//
//		func1(root->left, res);
//		func1(root->right, res);
//
//	}
//
//
//	int longestUnivaluePath(TreeNode* root) {
//		if (root == nullptr)
//			return 0;
//
//		int res = 0;
//		func1(root, res);
//		return res;
//	}
//};